package main.堆;

import java.net.Inet4Address;
import java.util.Stack;

/**
 * @author tmh
 * @date 2024/9/22 19:22
 * @description
 */
public class T739每日温度 {
    /**
     * 这个解法要爆
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        int len = temperatures.length;
        int[] result = new int[len];
        //双循环O(n平方)的时间复杂度，会超时
        for (int i = 0; i < temperatures.length; i++) {
            for (int j = i; j < temperatures.length; j++) {
                if (temperatures[j] > temperatures[i]) {
                    result[count++] = j - i;
                    break;
                }
                //表明这个数后面没有其他数字比这个数还要大了，那么就直接赋值为0
                if (j == len - 1) {
                    result[count++] = 0;
                }
            }
        }
        return result;
    }

    public int[] dailyTemperatures2(int[] temperatures) {
        //借助栈来保存小的元素
        Stack<Integer> stack = new Stack<>();
        int len = temperatures.length;
        int[] result = new int[len];
        //从右往左遍历
        for (int i = len - 1; i >= 0; i--) {
            int num = temperatures[i];
            //这里是temperatures[stack.peek()]，因为栈里面存的是当前元素后面元素的下标
            while (!stack.isEmpty()&&num>=temperatures[stack.peek()]){
                stack.pop();
            }
            if (!stack.isEmpty()){
                result[i]=stack.peek()-i;
            }
            stack.push(i);
        }
        return result;
    }

}
